翻訳と辞書 Words near each other ・ Skip Horack ・ Skip Humphrey ・ Skip James ・ Skip James (baseball) ・ Skip Jensen ・ Skip jive ・ Skip Jutze ・ Skip Kelly ・ Skip Kendall ・ Skip Kenney ・ Skip Konte ・ Skip Krake ・ Skip Lane ・ Skip lesion ・ Skip Lievsay ・ Skip list ・ Skip Lockwood ・ Skip Ltd. ・ Skip Manning ・ Skip Marley ・ Skip Martin ・ Skip McClendon ・ Skip Miller ・ Skip Minisi ・ Skip O'Brien ・ SKIP of New York ・ Skip Palenik ・ Skip Peete ・ SKIP Peru ・ Skip Pitlock Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Skip list ： ウィキペディア英語版 Skip list In computer science, a skip list is a data structure that allows fast search within an ordered sequence of elements. Fast search is made possible by maintaining a linked hierarchy of subsequences, each skipping over fewer elements. Searching starts in the sparsest subsequence until two consecutive elements have been found, one smaller and one larger than or equal to the element searched for. Via the linked hierarchy, these two elements link to elements of the next sparsest subsequence, where searching is continued until finally we are searching in the full sequence. The elements that are skipped over may be chosen probabilistically or deterministically,〔 (alternative link )〕 with the former being more common. == Description == A skip list is built in layers. The bottom layer is an ordinary ordered linked list. Each higher layer acts as an "express lane" for the lists below, where an element in layer ''i'' appears in layer ''i''+1 with some fixed probability ''p'' (two commonly used values for ''p'' are 1/2 or 1/4). On average, each element appears in 1/(1-''p'') lists, and the tallest element (usually a special head element at the front of the skip list) in $\backslash log\_\; n\backslash ,$ lists. A search for a target element begins at the head element in the top list, and proceeds horizontally until the current element is greater than or equal to the target. If the current element is equal to the target, it has been found. If the current element is greater than the target, or the search reaches the end of the linked list, the procedure is repeated after returning to the previous element and dropping down vertically to the next lower list. The expected number of steps in each linked list is at most 1/''p'', which can be seen by tracing the search path backwards from the target until reaching an element that appears in the next higher list or reaching the beginning of the current list. Therefore, the total ''expected'' cost of a search is $(\backslash log\_\; n)/p,\backslash ,$ which is $\backslash mathcal(\backslash log\; n)\backslash ,$ when ''p'' is a constant. By choosing different values of ''p'', it is possible to trade search costs against storage costs. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Skip list」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.